package
{
	public final class LCS
	{
		/**
		 * Calculates the lenght of LCS.
		 */
		public static function lcsLenght(x:String, y:String):int
		{
			const M:int = x.length
			const N:int = y.length;
			
			const opt:Vector.<Vector.<int>> = initTable(new Vector.<Vector.<int>>(), M+1, N+1);
			
			var i:int;
			var j:int;
			
			for (i = M-1; i >= 0; i--) 
				for (j = N-1; j >= 0; j--) 
					if (x.charAt(i) == y.charAt(j))
						opt[i][j] = opt[i+1][j+1] + 1;
					else 
						opt[i][j] = Math.max(opt[i+1][j], opt[i][j+1]);
			
			
			return opt[0][0];
		}
		
		/**
		 * Intstantiats new vector map
		 * */
		private static function initTable(opt:Vector.<Vector.<int>>, m:int, n:int):Vector.<Vector.<int>>
		{
			opt.length = m;
			opt.fixed = true;
			
			for(var i:int = 0; i < m; i++)
			{
				const vec:Vector.<int> = new Vector.<int>();
				vec.length = n;
				vec.fixed = true;
				opt[i] = vec;
			}
			
			return opt;
		}
	}
}